def max_heap(lst, n, i):
largest = i
# Calculating positions of left and right children
left = i * 2 + 1
right = i * 2 + 2
# Comparing the largest value to the left child
if left < n and lst[largest] < lst[left]:
largest = left
# Comparing the largest value to the right child
if right < n and lst[largest] < lst[right]:
largest = right
# Checking if largest index has been changed
# No need to swap elements or call function recursively if largest element was not changed
if largest != i:
# Swapping the values of the parent with the largest element
lst[largest], lst[i] = lst[i], lst[largest]
# Call function recursively to check children values
max_heap(lst, n, largest)Algorithims Heap Project
Hannah Butsko, Emma Horton, Arianne Pozzi, Matthew Wilcox
Purpose
- Process Student Applications
- Prioritize them based on various criteria
- Make admission offers to most qualified/preferred candidates
Max Heap Implemenation
Add a new value to the heap
def add_heap(lst, value):
lst.append(value) # Add the new value to the end of the heap
idx = len(lst) - 1 # Get the index of the newly added element
# Moving the newly added element up the tree as long as it's greater
# than its parent, maintaining the max heap property
while idx > 0:
parent_index = (idx - 1) // 2
if lst[idx] > lst[parent_index]:
lst[idx], lst[parent_index] = lst[parent_index], lst[idx]
idx = parent_index
else:
breakPop max heap implementation
def pop_max_heap(lst):
# Checking if list is empty
if not list:
return "The array is empty"
# Checking if there is only one element in the list
if len(lst) == 1:
return lst.pop()
# Maximum element
max_elem = lst[0]
# Last element
last = lst.pop()
if lst:
# Moving the last element to the root position
lst[0] = last
index = 0
n = len(lst)
# Restore the tree by bringing down the element
max_heap(lst, index, n)
# Returning the maximum element that was removed
return max_elemPrioritizing each student
def priority(payload, idx):
lst_priority = [
1 if payload["student_type"] == "Graduate" else 0,
1 if payload["computer_science"] is True else 0,
1 if payload["math"] is True else 0,
payload["year"], # Closer students are graduating - higher the priority
-payload["orientation_day"], # Reversing the orientation day value to give priority to students that register earlier
idx # Unique identifier of each student
]
return lst_priorityProcessing each student and admitting by priority criteria
def process_admissions(payload):
lst = []
admitted_students = [] # Initialize a list for admitted students
# Enumerating through student requests and prioritizing them
for idx, student in enumerate(payload):
priority_student = priority(student, idx)
add_heap(lst, priority_student) # Adding every priority to our max heap
# Admitting students up to a limit 25 based on max heap priorities
while len(admitted_students) < 25 and len(lst) > 0:
_, computer_science, math, year, orientation_day, idx = pop_max_heap(lst)
admitted_students.append(idx)
return admitted_studentsMaking offers to admitted students if places become available
def make_offers(payload, admitted_students, dropouts):
offers = []
# Checking for admitted students who haven't dropped the class
for idx, request in enumerate(payload):
if idx in admitted_students and idx not in dropouts:
offers.append(request)
# Filling empty spots with the most qualified students
while len(offers) < 25:
# Checking for the next most qualified student who hasn't been previously admitted
next_student = None
for index, request in enumerate(payload):
if index not in admitted_students and index not in dropouts:
if next_student is None or priority(request, index) > priority(next_student, index):
next_student = request
# If no more qualified students are available, break the loop
if next_student is None:
break
# Marking the student as admitted and add them to the offers list
admitted_students.append(payload.index(next_student))
offers.append(next_student)
return offersFunction that organizes student payload into a dictionary
We organized each student into a dictionary to use within the functions to retain all of the students data while assigning a priority
def student_data(name, student_type, computer_science, math, year, orientation_day, email, street, city, state, zip_code):
return {"name": name,
"student_type": student_type,
"computer_science": computer_science,
"math": math,
"year": year,
"orientation_day": orientation_day,
"email": email,
"Street Address": street,
"City": city,
"State": state,
"ZIP Code": zip_code}Make a random fake data set of size n
Using the faker package we built a function to create random students to populate our school to test our functions in createing priority queues.
def random_student_admission(size=40):
# Initialize Faker
fake = Faker()
# Create list of student_data dicts
student_list = []
for individual in range(0, size):
name = fake.name()
student_type = np.random.choice(['Undergraduate', 'Graduate', 'Auditor'])
computer_science = np.random.choice([True, False])
math = np.random.choice([True, False])
year = np.random.randint(0, 5)
orientation = np.random.randint(1, 6)
fake_email = fake.free_email()
fake_address = fake.street_address()
fake_city = fake.city()
fake_state = fake.state()
fake_zip = fake.postcode()
student_list.append(
student_data(name, student_type, computer_science, math, year, orientation, fake_email, fake_address, fake_city, fake_state, fake_zip))
return student_listCreate Admited Sutdents List
We first create a list of admited students. We select the size of our class and generate a random class of that size. In this case we do 38/
Create Admited Sutdents List
We then process them through admissions leaving us with a table of admitted students.
name student_type computer_science math year \
0 Michael Duncan Auditor True False 0
1 Jessica Thomas Auditor True False 4
2 Julie White Undergraduate False False 3
3 Melissa Pitts MD Undergraduate True True 0
4 Timothy Smith Auditor True True 0
5 Autumn Gutierrez MD Undergraduate True True 3
6 Joseph Williams Auditor True False 2
7 Kayla Benson Auditor False False 1
8 Michael Thompson Auditor True True 2
9 Frank Hobbs MD Undergraduate False False 3
10 William Dominguez Undergraduate False False 4
11 Todd Lozano Auditor True True 1
12 James Myers Undergraduate True False 1
13 James Curry Undergraduate False True 1
14 Vanessa Miller Undergraduate True False 1
15 Harry Phelps Undergraduate True False 2
16 Matthew Morrow Undergraduate True True 1
17 Tina Leach Auditor True True 2
18 Brian Stephens Graduate True False 1
19 Collin Mcpherson Graduate False True 4
20 Jeffrey Flowers Auditor True True 3
21 Andrew Harris Undergraduate False True 0
22 Patricia Collins DDS Undergraduate True False 2
23 Deborah Lopez Undergraduate False True 1
24 Jasmine Brown Auditor True True 1
orientation_day email \
0 1 eturner@yahoo.com
1 5 michael64@yahoo.com
2 3 jjones@yahoo.com
3 5 westjudy@yahoo.com
4 5 hickschristopher@yahoo.com
5 4 sjackson@gmail.com
6 3 rodneyglover@gmail.com
7 2 jamesteresa@yahoo.com
8 4 smithmichele@yahoo.com
9 5 karen98@gmail.com
10 4 hernandezjohn@yahoo.com
11 4 qbowman@hotmail.com
12 2 qparks@yahoo.com
13 2 alexandermiller@gmail.com
14 1 blairbrandy@yahoo.com
15 4 tinaortega@yahoo.com
16 5 lindseymcconnell@gmail.com
17 5 raymondquinn@hotmail.com
18 2 howens@hotmail.com
19 1 williamselizabeth@gmail.com
20 1 kaylacasey@yahoo.com
21 2 ashleyhouston@yahoo.com
22 3 edwardseduardo@yahoo.com
23 2 williamsbryan@hotmail.com
24 4 zacharyclark@hotmail.com
Street Address City State \
0 23491 Jessica Trace Lake Cherylmouth New Jersey
1 138 Sandra Expressway Kennethstad New Jersey
2 19110 Marcus Canyon Apt. 390 New William Indiana
3 96466 Gregory Radial Suite 925 Millerview Idaho
4 6644 Lewis Bypass West Natalieborough Arizona
5 506 Juan Parks Suite 558 Kevinfurt Kentucky
6 6507 Camacho Greens Cassandraport Mississippi
7 1343 Daisy Ville Apt. 487 East Jamesland Nebraska
8 37337 Watson Burg Apt. 410 Zacharyberg West Virginia
9 74273 Samantha Mission Tinamouth California
10 60809 Curtis Lake Suite 803 Youngland North Carolina
11 42549 Wanda Village Grimesview Montana
12 48608 Jones Estate South Marissaport New Hampshire
13 899 Hill Passage Suite 465 Port Nicole Florida
14 2704 Austin Square New William North Dakota
15 6356 Lane Mission Apt. 699 Monicashire Wyoming
16 0400 Rick Mount Suite 453 Daltonland North Carolina
17 89375 Perez Falls Matthewview New Hampshire
18 56720 Schmidt Fields Crosbystad Tennessee
19 04263 Harvey Fork Suite 399 West Michael Kansas
20 26308 David Route Suite 316 New Nathanhaven Louisiana
21 979 Noah Causeway Suite 639 Kennedyfort Vermont
22 8873 Graham Fall Wolfehaven North Carolina
23 175 Lynch Fort Apt. 265 Ortizton Alabama
24 785 Lewis Motorway Port Jennifer South Carolina
ZIP Code
0 45803
1 18909
2 39284
3 63974
4 82823
5 29256
6 54937
7 42775
8 84134
9 52366
10 06302
11 82295
12 58256
13 14365
14 74771
15 23211
16 02388
17 12148
18 07100
19 30133
20 00544
21 83776
22 37556
23 62939
24 90873 Simulating dropouts
We are now goint to simulate two students, {python} admitted_students[3]
Making offers if places become available
This is now the final class after we had 2 dropouts.
name student_type computer_science math year \
0 Michael Duncan Auditor True False 0
1 Jessica Thomas Auditor True False 4
2 Julie White Undergraduate False False 3
3 Melissa Pitts MD Undergraduate True True 0
4 Autumn Gutierrez MD Undergraduate True True 3
5 Kayla Benson Auditor False False 1
6 Michael Thompson Auditor True True 2
7 Frank Hobbs MD Undergraduate False False 3
8 William Dominguez Undergraduate False False 4
9 Todd Lozano Auditor True True 1
10 James Myers Undergraduate True False 1
11 James Curry Undergraduate False True 1
12 Vanessa Miller Undergraduate True False 1
13 Harry Phelps Undergraduate True False 2
14 Matthew Morrow Undergraduate True True 1
15 Tina Leach Auditor True True 2
16 Brian Stephens Graduate True False 1
17 Collin Mcpherson Graduate False True 4
18 Jeffrey Flowers Auditor True True 3
19 Andrew Harris Undergraduate False True 0
20 Patricia Collins DDS Undergraduate True False 2
21 Deborah Lopez Undergraduate False True 1
22 Jasmine Brown Auditor True True 1
23 Damon Anderson Graduate False False 3
24 Kerri Oliver Graduate True False 2
orientation_day email \
0 1 eturner@yahoo.com
1 5 michael64@yahoo.com
2 3 jjones@yahoo.com
3 5 westjudy@yahoo.com
4 4 sjackson@gmail.com
5 2 jamesteresa@yahoo.com
6 4 smithmichele@yahoo.com
7 5 karen98@gmail.com
8 4 hernandezjohn@yahoo.com
9 4 qbowman@hotmail.com
10 2 qparks@yahoo.com
11 2 alexandermiller@gmail.com
12 1 blairbrandy@yahoo.com
13 4 tinaortega@yahoo.com
14 5 lindseymcconnell@gmail.com
15 5 raymondquinn@hotmail.com
16 2 howens@hotmail.com
17 1 williamselizabeth@gmail.com
18 1 kaylacasey@yahoo.com
19 2 ashleyhouston@yahoo.com
20 3 edwardseduardo@yahoo.com
21 2 williamsbryan@hotmail.com
22 4 zacharyclark@hotmail.com
23 2 cynthia61@yahoo.com
24 3 hannah95@hotmail.com
Street Address City State ZIP Code
0 23491 Jessica Trace Lake Cherylmouth New Jersey 45803
1 138 Sandra Expressway Kennethstad New Jersey 18909
2 19110 Marcus Canyon Apt. 390 New William Indiana 39284
3 96466 Gregory Radial Suite 925 Millerview Idaho 63974
4 506 Juan Parks Suite 558 Kevinfurt Kentucky 29256
5 1343 Daisy Ville Apt. 487 East Jamesland Nebraska 42775
6 37337 Watson Burg Apt. 410 Zacharyberg West Virginia 84134
7 74273 Samantha Mission Tinamouth California 52366
8 60809 Curtis Lake Suite 803 Youngland North Carolina 06302
9 42549 Wanda Village Grimesview Montana 82295
10 48608 Jones Estate South Marissaport New Hampshire 58256
11 899 Hill Passage Suite 465 Port Nicole Florida 14365
12 2704 Austin Square New William North Dakota 74771
13 6356 Lane Mission Apt. 699 Monicashire Wyoming 23211
14 0400 Rick Mount Suite 453 Daltonland North Carolina 02388
15 89375 Perez Falls Matthewview New Hampshire 12148
16 56720 Schmidt Fields Crosbystad Tennessee 07100
17 04263 Harvey Fork Suite 399 West Michael Kansas 30133
18 26308 David Route Suite 316 New Nathanhaven Louisiana 00544
19 979 Noah Causeway Suite 639 Kennedyfort Vermont 83776
20 8873 Graham Fall Wolfehaven North Carolina 37556
21 175 Lynch Fort Apt. 265 Ortizton Alabama 62939
22 785 Lewis Motorway Port Jennifer South Carolina 90873
23 428 Darren View Brandonport California 73720
24 8345 Krystal Island West Ashleystad Indiana 05262 Power BI Implementation
Power Bi - Data Model
Power Bi - Not Admitted Students
Power Bi - Admitted Students
Power Bi - Acceptance email
